package done.easy_801_900;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 872. Leaf-Similar Trees 叶子相似的树
 * <p>
 * 请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
 * <p>
 * 给定树
 * 3
 * /      \
 * 5        1
 * /   \    /   \
 * 6    2   9     8
 * / \
 * 7   4
 * <p>
 * 与下面的树相似
 * <p>
 * 3
 * /       \
 * 5          1
 * /    \     /    \
 * 6     7    4      2
 * /    \
 * 9      8
 * <p>
 * 举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。
 * 如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
 * 如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回
 * true；否则返回 false 。
 *
 * @author 大硕
 * 2019-04-11 8:27 AM
 **/
@SuppressWarnings("all")
public class Leaf_SimilarTrees {

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        // 190411 first
        return false;
    }

    @Test
    public void test() {
        TreeNode source = new TreeNode(3,
                new TreeNode(5,
                        6, new TreeNode(2,
                        7, 4)), new TreeNode(1,
                9, 8));

        TreeNode target = new TreeNode(3,
                new TreeNode(5,
                        6, 7), new TreeNode(1,
                4, new TreeNode(2,
                9, 8)));
        info(leafSimilar(source, target));
    }
}






































/*
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
    List<Integer> l1 = new ArrayList<>();
    List<Integer> l2 = new ArrayList<>();
    leafs(root1, l1);
    leafs(root2, l2);
    return l1.equals(l2);
}

public void leafs(TreeNode node, List<Integer> l) {
    if (node == null) {
        return;
    } else if (node.left == null && node.right == null) {
        l.add(node.val);
    }
    leafs(node.left, l);
    leafs(node.right, l);
}
*/
